1. Field of the Invention
The invention relates generally to a method and system for routing data packets through a packet communication network.
Packet communications is a form of data communications whereby segments or packets of data are routed with error checking and confirmation of receipt directly or relayed via relay stations between a source node or station and a destination node or station. Several methods of data packet routing are known. According to one method, the address in the header of the packet is used as an index to a directory of packet routing lists. Packet routing lists must be prepared with knowledge about the location of each node in the network. Each node is identified by a header identifier. A packet routing list consists of an ordered list of packet node identifiers or call signs. Directory-based routing schemes require continued maintenance and communication of network interconnectivity information employed in the directory. Each of these functions drains network resources and can become intractable in a large network. However, one of the advantages of directory-based routing techniques is that it permits optimization of routing for a wide variety of network parameters, including data delay, throughput, reliability, priority and the like.
Another basic routing technique is the nondirectory-based routing technique. In nondirectory-based routing, the complexities associated with routing techniques are avoided. There is no connectivity information, which thus simplifies construction of each node. However, nondirectory-based routing techniques do not permit network parameter optimization.
2. Description of the Relevant Literature
The following patents were uncovered in a search of prior art with respect to the subject invention:
______________________________________ Inventor U.S. Pat. No. Date of Patent ______________________________________ Otomo et al. 4,074,232 February 14, 1978 Sanders, Jr. et al. 4,135,156 January 16, 1979 deCouasnon et al. 4,168,400 September 18, 1979 Maxemchuk 4,516,239 May 7, 1985 Cohen et al. 4,525,830 June 25, 1985 Maxemchuk et al. 4,534,024 August 6, 1985 Gable et al. 4,550,402 October 29, 1985 George et al. 4,644,532 February 17, 1987 Lea et al. 4,661,947 April 28, 1987 Lambarelli et al. 4,663,758 May 5, 1987 ______________________________________
The Maxemchuk patents of Bell Laboratories teach the use of data packet systems over cable television networks and also teach the use of variable length packets for voice. The George et al. patent to IBM teaches the use of routing notes utilizing the topology of the network. The Sanders patent teaches the use of satellite communications whereby messages are routed via a local relay station. The Lea patent to Bell Labs teaches the use of a self-routing packet switching network. None of these patents suggest routing based on a node identifier which employs absolute geographic location indicia in the identifier for use in establishing routing.
The remaining patents above relate to the general state of the art of packet communication.
A noteworthy background reference related to radio-based packet communications is the published standard for AX.25 entitled "AX.25 Amateur Packet-Radio Link-Layer Protocol," Version 2.0 (October 1984), Publication No. 56, American Radio Relay League, Inc., Newington, Conn. This protocol is directed to the link layer or level 2 of the International Organization for Standardization (ISO) seven-layered reference model of Open Systems Interconnection (OSI) and is based on the CCITT X.25 level 2 LAPB protocol standard of Recommendation AX.25 of the International Telegraph and Telephone Consultative Committee (CCITT). The AX.25 protocol differs from the X.25 protocol in that the AX.25 protocol provides for repeater stations and repeater linking at the link layer, and specifically up to eight repeater stations under Version 2.0. Whereas the ability to address a destination via a prescribed repeater chain proved to be an advance for link layer protocols, the link remains susceptible to breakdown in linking if the chain is interrupted or changed. As will be explained hereinbelow, the present invention represents a substantial departure from an addressing protocol based on explicitly predefining a routing.
In a theoretical paper first published in March of 1987, less than one year prior to the effective filing date of this application, entitled "Routing and Addressing Problems in Large Metropolitan-scale Internetworks" by Gregory G. Finn, ISI Research Report ISI/RR-87-180 March 1987 (Marina del Rey, Calif.) there appears a description of a Cartesian routing protocol of one form. The Cartesian routing protocol described therein associates a semi-unique ordered Cartesian location with each gateway (node) as part of a Cartesian address combining a location element and a gateway identifier. Position is represented by this location identifier and a metric distance is calculated between two such locations based on the location identifier. Specific reference is made therein to the use of latitude and longitude values as the basis of the Cartesian coordinate system. A hierarchy is suggested therein based on the hop range of reachable nodes in the network. The hierarchy suggested therein is used in conventional telephone networking protocols. The Finn paper is believed to be the only description of a packet routing protocol suggesting use of Cartesian geographical coordinates. Notwithstanding, this paper is not prior art to the subject invention under the patent laws of the United States.